package digui;

import java.util.Arrays;
//快速排序
public class DiGui {
    public static void main(String[] args) {
        int[] a = {3, 4, 6, 1, 2, 4, 2};
        System.out.println("Arrays.toString(a) = " + Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println("Arrays.toString(a) = " + Arrays.toString(a));

    }

    public static void quickSort(int[] arr, int start, int end) {
        //1.数组可以排序
        if (start < end) {
            //1.排序数组的第0个元素为基准
            int base = arr[start];//3
            int left = start;//左指针
            int right = end;//右指针
              while (left < right)//left==right
            {
                //1.从右向左找，比base小，指针左移
                while (left < right && arr[right] >= base) {
                    right--;
                }
                //如果比基准值小，则替换left下标的值
                arr[left] = arr[right];


                //1.从左向右找，比base大，指针左移
                while (left < right && arr[left] <= base) {
                    left++;
                }
                //如果比基准值大，则替换right下标的值
                arr[right] = arr[left];
            }

            arr[left] = base;//基准值替换两个指针相遇位置的数据

            quickSort(arr, start, left - 1);//前半部分进行相同操作
            quickSort(arr, left + 1, end);
        }
    }
}